package cn.bouncyslime.algorithms.stack.infixToPostfix;

import java.util.*;

/**
 * 将中缀表达式转换为后缀表达式，其中表达式的操作数是字符，而不是数字
 * 测试到现在应该是没有问题的
 * @author 张一卓
 */
public class InfixToPostfix {

	/**
	 * 用来存放运算符的栈
	 */
	private Deque<Character> stack = new LinkedList<>();

	/**
	 * 设定运算符优先级的Map
	 */
	private final Map<Character, Integer> operatorPriority = new HashMap<>();

	/**
	 * 存储所有运算符的List
	 */
	private final List<Character> operatorList = new ArrayList<>();

	/**
	 * 将中缀表达式转换为后缀表达式的结果List
	 */
	private List<Character> outputList = new ArrayList<>();
	
	/**
	 * 用来初始化运算符优先级Map{@link #operatorPriority}和存有所有运算符的List{@link #outputList}
	 */
	public InfixToPostfix() {
		operatorPriority.put('(', 1);
		operatorPriority.put(')', 1);
		operatorPriority.put('*', 2);
		operatorPriority.put('/', 2);
		operatorPriority.put('+', 3);
		operatorPriority.put('-', 3);
		operatorList.add('(');
		operatorList.add(')');
		operatorList.add('+');
		operatorList.add('-');
		operatorList.add('*');
		operatorList.add('/');
	}
	
	/**
	 * 用来将中缀表达式转换为后缀表达式，转换的结果为存储所有字符的List，之后将该List转换为数组输出
	 * @param input 中缀表达式字符串
	 * @return 存储有后缀表达式各个字符的char数组
	 */
	public Character[] change(String input) {
		char[] inputChar = input.toCharArray();
		for (int i = 0; i < inputChar.length; i++) {
			// 如果输入字符不是运算符
			if (!operatorList.contains(inputChar[i])) {
				outputList.add(inputChar[i]);
			}else {
				// 运算符栈是否为空栈
				if (stack.isEmpty()) {
					stack.push(inputChar[i]);
				}else {
					if (inputChar[i] != ')') {
						// 当压入栈的运算符的优先级比栈顶等级低或者相等，则将前面的运算符抛出栈并存放到后缀表达式List中，直到压入栈的运算符优先级大于栈顶运算符优先级
						while (!stack.isEmpty() && operatorPriority.get(stack.peek()) != 1 && operatorPriority.get(inputChar[i]) >= operatorPriority.get(stack.peek())) {
							outputList.add(stack.pop());
						}
						// 排除了运算符优先级不小于自己的运算符之后将自己压入栈
						stack.push(inputChar[i]);
					}else { // 如果碰到闭括号
						// 抛出栈中开括号之前的元素，括号不做输出
						while (stack.peek() != '(') {
							outputList.add(stack.pop());
						}
						stack.pop();
					}
				}
			}
			// 遍历到输入字符串截尾之后，如果栈中还有元素则
			while (i == inputChar.length-1 && !stack.isEmpty()) {
				outputList.add(stack.pop());
			}
			System.out.println("当前遍历的表达式中元素的位置为 " + i);
			System.out.println("stack: " + stack);
			System.out.println("outputList: " + outputList);
			System.out.println();
		}
		return outputList.toArray(new Character[0]);
	}
	
	public static void main(String[] args) {
		String input = "a+b*c+(d*e+f)*g";
//		String input = "a*b-c+d+(e/f-g)*h";
//		String input = "(a*b-c)*d+e";
//		String input = "(a*b-c)*d+e+(f/g-h)";
//		String input = "(a+(b*c-d)-e)+f/g";
		InfixToPostfix infixToPostfix = new InfixToPostfix();
		System.out.println(Arrays.toString(infixToPostfix.change(input)));
	}
	
}
